package someTestExcemple.huaweiOd.binarySearch;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

//华为OD机试 - 最少交付时间 - 二分查找、回溯（Java 2025 A卷 200分）
//https://blog.csdn.net/guorui_java/article/details/146798220
/*
* 回溯算法的基本思想是深度优先搜索（DFS），
* 它会构建一棵解空间树，从根节点开始，逐步深入树的分支，尝试所有可能的解决方案。
* 在搜索过程中，如果发现当前的部分解不可能得到有效的完整解，
* 就回溯到上一个节点，换一条路径继续搜索，
* 避免对不可能产生解的子树进行无效搜索，从而提高搜索效率。*/
public class MinimumTimeToDelivery {
    /*    具体步骤：
        任务排序：首先按照工作量从大到小对需求进行排序。
        初始化工作量数组：创建一个数组（或列表），用以记录每位开发人员当前的工作量。
        贪心分配任务：依次将最大的任务分配给当前工作量最小的开发人员。
        通过这种方式，我们尽可能保证每个人的负载都接近平均，但尽量让工作量较大的任务先分配，从而尽早开始执行耗时较长的任务。
        一个有效的方法是使用“最短处理时间优先”（SPT，Shortest Processing Time first）策略，
        结合“最长任务优先分配”（Largest Task First allocation）以及“贪心算法”，使得总体完成时间最短。
    //就是，先分配工作量大的任务，然后当前任务总时间少的人，优先被分配，
    */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取工作量和员工数
        String[] workloadStr = scanner.nextLine().split(" ");
        int[] workloads = Arrays.stream(workloadStr).mapToInt(Integer::parseInt).toArray();
        int numEmployees = Integer.parseInt(scanner.nextLine());

        // 计算最短完成时间
        int minDays = calculateMinimumDays(workloads, numEmployees);
        int minDays_2 = calculateMinimumDays_2(workloads, numEmployees);
        System.out.println(minDays);
        System.out.println(minDays_2);
    }

    private static int calculateMinimumDays(int[] workloads, int numEmployees) {
        // 将任务按照工作量从大到小排序
        //这里从小到大
        Arrays.sort(workloads);
        // 初始化员工工作天数数组-值为当前工作量
        int[] employeeLoad = new int[numEmployees];

        // 从最大工作量任务开始分配
        for (int i = workloads.length - 1; i >= 0; i--) {
            //默认0号员工当前工作量最小
            int minLoadIndex = 0;
            // 找到当前工作量最小的员工
            for (int j = 1; j < numEmployees; j++) {
                if (employeeLoad[j] < employeeLoad[minLoadIndex]) {
                    minLoadIndex = j;
                }
            }
            // 分配任务给该员工
            employeeLoad[minLoadIndex] += workloads[i];
        }

        // 找出最大的工作量，即为完成所有任务的最少天数
        int maxDays = 0;
        for (int load : employeeLoad) {
            maxDays = Math.max(maxDays, load);
        }
        return maxDays;
    }

    //方法2 -二分查找
    // 基本思路是先确定完成所有任务所需天数的上下界，然后在这个范围内进行二分查找，判断在给定天数内能否完成所有任务，逐步缩小范围，最终找到最少的天数。
    private static int calculateMinimumDays_2(int[] workloads, int numEmployees) {
        // 确定二分查找的左右边界
        int left = Arrays.stream(workloads).max().getAsInt(); // 左边界为最大的单个任务工作量
        int right = Arrays.stream(workloads).sum(); // 右边界为所有任务工作量之和 -只有一个员工-都他做
        int minday = Integer.MAX_VALUE;

        //todo 我个人喜欢写 left<=right 然后 right = mid-1;或者 left=mid+1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(workloads, numEmployees, mid)) {
                right = mid;
                minday = Math.min(minday,mid);
            } else {
                left = mid + 1;
            }
        }
        return minday;
    }

    private static boolean canFinish(int[] workloads, int numEmployees, int days) {
        int currentEmployees = 1;
        int currentWorkload = 0; //至少需要的员工数-才能在days天内完成任务
        for (int workload : workloads) {
            if (currentWorkload + workload > days) {
                currentEmployees++;
                //新加员工接手currentWorkload
                currentWorkload = workload;
            } else {
                //还没超可以干
                currentWorkload += workload;
            }
        }
        return currentEmployees <= numEmployees;
    }
}
